#include <stdio.h>

#define MAX_N  10
#define MAX_M   3

int count = 0;
int cassette[MAX_N + 2][MAX_M + 2] = {0};

//判断第n行第m列的卡座是否可以坐
bool canSit(int n, int m)
{
    if (cassette[n-1][m-1] | cassette[n-1][m] | cassette[n-1][m+1]) return false;
    if (cassette[n][m-1] | cassette[n][m+1]) return false;
    if (cassette[n+1][m-1] | cassette[n+1][m] | cassette[n+1][m+1]) return false;
    return true;
}

void a(int n, int k, int m)
{
    if (n < 1)  return;         //所有行都已尝试过
    if (k == 0) { count++; }    //k个员工均已安排好座位
    else {
        while (m <= MAX_M) {
            if (canSit(n, m)) {     //如果第n行的第m列的卡座可以坐
                cassette[n][m] = 1; //将第n行的第m列的卡座置为已坐
                a(n, k-1, m+1);     //从第n行的第m+1列尝试下一个员工可以坐
                cassette[n][m] = 0; //回溯时，将第n行的第m列的卡座置为未坐
            }
            m++;
        }
        a(n - 1, k, 1);     //尝试下一行的部署方法
    }
}

int main()
{
    int n, k;
    for (n = 1; n <= MAX_N; n++) {
        for (k = 1; k <= MAX_N; k++) {
            count = 0;
            a(n, k, 1);
            printf("%8d, ", count);
        }
        printf("\n");
    }
}